#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/14
# @Author   :Changshu
# @File     :Exercise_575.py
# 575. 分糖果

# 给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。
# 你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

'''法一：排序后遍历，效率太低
class Solution:
	def distributeCandies(self, candyType: list) -> int:
		if candyType==[]:
			return 0
		candyType.sort()
		count=0
		pre=-1
		for n in candyType:
			if n!=pre:
				count+=1
				pre=n
		if count>len(candyType)//2:
			return len(candyType)//2
		return count
'''


'''法二：用集合'''
class Solution:
	def distributeCandies(self, candyType: list) -> int:
		s=set()
		for n in candyType:
			s.add(n)
		return min(len(s),len(candyType)//2)


if __name__ == '__main__':
	solution=Solution()
	# candies = [1, 1, 2, 3]			# 2
	candies = [1,1,1,1,1,1,1,8,9,10]
	print(solution.distributeCandies(candies))
